1. Field of the Invention
This invention relates to the field of encryption, and more particularly relates to a method and system for pipelined decryption.
2. Description of the Related Art
Encryption refers to the process of encoding information (plaintext) into a form that is unreadable (ciphertext) without decoding (decryption). Thus, an unintended third party is unable to recover the meaning of the message, if that party has intercepted the encrypted message. Conversely, decryption refers to the process of recovering the plaintext of an encrypted message after the encrypted message has been received.
In today's technology environment, many applications for encryption techniques exist. For example, such techniques can be used in a network such as the Internet. Such a network may connect thousands of network nodes, including routers, bridges, hubs, servers, and user terminals, which can lead to opportunities for information transmitted across such networks to be diverted surreptitiously. As a result of this susceptibility of messages in transit to interception by unintended third parties, security can be of great concern in transmitting a message from a source node to a destination node in such a network. This problem is typically addressed by encrypting a message at the source node, prior to transmission, and then decrypting the message at the destination node, after reception.
Another application of encryption is the protection of a programmable logic device's (PLD's) configuration bitstream from examination. To do so, software can be designed to encrypt a configuration bitstream that is stored off-chip. The PLD is then made to include a decryptor capable of decrypting the encrypted configuration bitstream, and so allow its use in configuring the PLD.
Commonly, encryption/decryption algorithms use a key selected by the user to transform a block of some fixed length into the corresponding encrypted (decrypted) block. If the data to be encrypted (decrypted) is longer than the fixed length, the data may be divided into blocks of the requisite length and the algorithm applied to each block successively. FIGS. 1 and 2 (described subsequently) depict such a process, in which the block length is fixed (e.g., at 128 bits). The functions described in connection therewith are well known, and are further described in various publications (e.g., NIST Special Publication 800-38A, Recommendation for Block Cipher Modes of Operation: Methods and Techniques, 2001 Edition, by M. Dworkin).
FIG. 1 is a set of process diagrams illustrating examples of an encryption process (depicted in FIG. 1 as an encryption process 100) and a decryption process (depicted in FIG. 1 as a decryption process 110) according to the prior art. FIG. 1 depicts the basic operations performed under the Advanced Encryption Standard (AES) Electronic Codebook (ECB) Mode (Federal Information Processing Standard (FIPS) Publication 197), in which plaintext is unencrypted data and ciphertext is encrypted data. Encryption process 100 begins with the reception of plaintext 120. Plaintext 120 is divided into a number of input blocks (represented in FIG. 1 by an input block 122). Input block 122 is provided to an encryption unit 124 for encryption. Encryption unit 124 encrypts input block 122, and provides this encrypted information as a number of output blocks (represented in FIG. 1 by an output block 126). These output blocks are combined to form ciphertext 128.
In a similar manner, decryption process 110 takes in ciphertext 130 as a number of ciphertext blocks (represented by ciphertext block 132). Ciphertext block 132 is provided to a decryption unit 134. Decryption unit 134 decrypts the encrypted information, and outputs the result as an output block 136. Output block 136, representing a number of such output blocks, is combined with these other output blocks, in order to produce plaintext 138.
A weakness of this method is that, for any given key, identical plaintext blocks are always encrypted into the same ciphertext, so that patterns of repeated plaintext blocks may be inferred by detection of repeated ciphertext blocks. To disguise the repetition of plaintext blocks, encryption/decryption algorithms can use Cipher Block Chaining (CBC) Mode, in which the ciphertext for the prior block is exclusive-or'ed (XOR'd) with the current block before encryption and after decryption. Such a process is presented and described in connection with FIG. 2.
FIG. 2 is a block diagram illustrating the Cipher Block Chaining (CBC) mode of encryption and decryption according to NIST recommendations (NIST Special Publication 800-38A) and other sources. A secure system 200 includes an encryption unit 205 and a decryption unit 210. Encryption unit 205 encrypts plaintext into ciphertext for secure communication to decryption unit 210, which then decrypts the ciphertext into plaintext. These components are now described in greater detail.
Encryption unit 205 receives plaintext data (not shown) as a number of data blocks 210(1)-(N). Each of data blocks 210(1)-(N) is pre-processed to generate input blocks 215(1)-(N). Each of input blocks 215(1)-(N) is then encrypted by a corresponding one of encryption units 220(1)-(N). Encryption units 220(1)-(N) output the encrypted version of a corresponding one of input blocks 215(1)-(N), as a corresponding one of ciphertext blocks 225(1)-(N). Ciphertext blocks 225(1)-(N) are then ready for communication to decryption unit 210.
Each of ciphertext blocks 225(1)-(N-1) is also input to a corresponding one of exclusive-OR (XOR) units 230(1)-(N) (specifically, a corresponding one of XOR units 230(2)-(N)). XOR unit 230(1) is a special case (having no preceding ciphertext block to take as input), and so takes an encryption initialization vector 235 as its input. Thus, the pre-processing performed on each of data blocks 210(1)-(N) is an XOR performed by each of XOR units 230(1)-(N) between a corresponding one of data blocks 210(2)-(N) and a preceding one of ciphertext blocks 225(1)-(N-1) (the exception being the case of data block 210(1), as noted).
As can be seen in FIG. 2, decryption unit 210 operates in a manner similar to that of encryption unit 205. Each of ciphertext blocks 225(1)-(N) is received at decryption unit 210 as a corresponding one of ciphertext blocks 240(1)-(N). Each of ciphertext blocks 240(1)-(N) is decrypted by a corresponding one of decryption units 245(1)-(N). The decryption of ciphertext blocks 240(1)-(N) by a corresponding one of decryption units 245(1)-(N) results in a corresponding one of output blocks 250(1)-(N). Each of output blocks 250(1)-(N) are then provided to a corresponding one of XOR units 255(1)-(N). Each of XOR units 255(2)-(N) also takes as an input the ciphertext block received by the preceding stage (specifically, the preceding one of ciphertext blocks 240(1)-(N-1)), with XOR 255(1) being the exception, in taking as its input a decryption initialization vector 260 (in addition to output block 250(1)). As is known, initialization vector 260 is the same as initialization vector 235.
As will be appreciated, a given one of data blocks 210(1)-(N) cannot be processed and provided to a corresponding one of input blocks 215(1)-(N), until the preceding data block is encrypted (and so the requisite ciphertext block is available) (save for data block 210(1), which begins the process by using encryption initialization vector 235 in the exclusive-OR process). As will also be appreciated, since plaintext data is broken into data blocks, the time required to encrypt the data is dependent on the number of data blocks into which the plaintext data is broken into (and so the number of encryption stages employed).
In a similar fashion, the exclusive-OR'ing of each output block with its preceding ciphertext block in decryption unit 210 results in a corresponding one of data blocks 265(1)-(N). As will be appreciated, in certain scenarios, ciphertext blocks 240(1)-(N) is received in a staggered fashion, leaving later ones of decryption units 245(1)-(N) waiting for some period of time. If ciphertext blocks 240(1)-(N) are received in such a staggered fashion, the delays noted previously with regard to the operation of encryption unit 205 will also be experienced within decryption unit 210. Alternatively, if ciphertext blocks 225(1)-(N) are buffered until all such ciphertext blocks are available, ciphertext blocks 240(1)-(N) will be received at the same time. In either case, however, the infrastructure required by such design will be substantial in relative terms.
What is therefore desired is a decryption architecture that is capable of decrypting standard encryption formats, while consuming a minimal (or acceptable) amount of resources in its implementation. Preferably, such an approach should allow the designer freedom in making design choices, by allowing the designer to trade off the size of such a design for the speed provided thereby.